Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach.

I enjoyed reading this paper and thought it was very well written. The one negative about the paper is that the results presented are somewhat simplistic (the author's acknowledge this point directly). The paper considers an interesting recent effort (specifically in the paper "The Case for Learned Index Structures") to use predictive machine learning models to improve the performance of basic data structures. In particular, this work focuses on the standard Bloom filter for quickly detecting set membership, possibly with some false positives. "The Case for Learned Index Structures" suggests a "learned" bloom filter, which essentially uses a learning pre-filter to guess if an input query is in the set of interest.

Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach. Papers published at the Neural Information Processing Systems Conference.